package cn.yoaket.algorithm;//package algorithm;
//
//import com.yoaker.unit.Point;
//import com.yoaker.unit.Polygon;
//
//import java.util.HashSet;
//import java.util.Set;
//
//public class ConvexHull {
//
//
//    public static double calculateBearingToPoint(double currentBearing, int currentX, int currentY, int targetX, int targetY) {
//        double angle;
//        int x = targetX - currentX;
//        int y = targetY - currentY;
//        angle = Math.atan2(x, y) * 180.0 / Math.PI - currentBearing;
//        return angle < 0 ? angle + 360 : angle;
//    }
//
//    public static Polygon getConvexHull(Polygon polygon) {
//        Set<Point> points = new HashSet<>(polygon.vertexes());
//        Set<Point> shellPoint = new HashSet<>();
//        Polygon shellPolygon = new Polygon();
//
//        Point minPoint = null;
//        double nowBearing;
//        double nextBearing;
//        double preBearing;
//        double nextLength;
//        Point nowPoint;
//        Point nextPoint = null;
//        if (!points.isEmpty()) {
//            //元素小于3个时，必是凸包直接返回
//            if (points.size() <= 4)
//                return polygon;
//
//            //求最左下元素
//            for (Point point : points) {
//                if (minPoint == null) {
//                    minPoint = point;
//                    continue;
//                }
//                if (minPoint.getX() > point.getX())
//                    minPoint = point;
//                else if (minPoint.getX() == point.getX()) {
//                    if (point.getY() < minPoint.getY())
//                        minPoint = point;
//                }
//            }
//
//            shellPoint.add(minPoint); //最左下元素定时凸包元素，加入集合
//            nowPoint = minPoint;
//            preBearing = 0; //之前凸包元素指向最近凸包元素的角度（相对与y轴顺时针）
//            while (true) {
//                nextBearing = 360;
//                nextLength = Double.MAX_VALUE;
//                for (Point point : points) {
//                    if (point.equals(nowPoint))
//                        continue;
//                    nowBearing = calculateBearingToPoint(preBearing, (int) nowPoint.getX(), (int) nowPoint.getY(), (int) point.getX(), (int) point.getY());
//                    if (nextBearing == nowBearing) {
//                        if (nextLength < (Math.pow(point.getX() - nowPoint.getX(), 2) + Math.pow(point.getY() - nowPoint.getY(), 2))) {
//                            nextLength = Math.pow(point.getX() - nowPoint.getX(), 2) + Math.pow(point.getY() - nowPoint.getY(), 2);
//                            nextPoint = point;
//                        }
//                    } else if (nextBearing > nowBearing) {
//                        nextLength = Math.pow(point.getX() - nowPoint.getX(), 2) + Math.pow(point.getY() - nowPoint.getY(), 2);
//                        nextBearing = nowBearing;
//                        nextPoint = point;
//                    }
//                }
//                if (minPoint.equals(nextPoint)) {
//                    break;
//                }
//                nowPoint = nextPoint;
//                preBearing += nextBearing;
//                shellPoint.add(nextPoint);
//            }
//
//        }
//        shellPolygon.add(shellPoint);
//        shellPolygon.sortByClock();
//        shellPolygon.sealed();
//
//        return shellPolygon;
//    }
//}
